Space Complexity

释义 Definition

空间复杂度：在算法分析中，用来描述算法在输入规模增长时所需额外内存/存储空间随之增长的趋势，通常用 Big-O（大 O 记号） 表示（如 O(1), O(n), O(n log n) 等）。它关注的是除输入本身之外，算法运行过程中占用的辅助空间（如递归栈、临时数组、哈希表等）。

发音 Pronunciation (IPA)

/speɪs kəmˈplɛksɪti/

例句 Examples

The space complexity of this algorithm is O(n).
这个算法的空间复杂度是 O(n)。

Although the time complexity is good, the space complexity becomes a problem when the dataset is huge.
虽然时间复杂度不错，但当数据集非常大时，空间复杂度就成了问题。

词源 Etymology

space（空间、内存空间）+ complexity（复杂性）。其中 complexity 源自拉丁语词根 complexus（意为“交织在一起的、由多部分组成的”），在计算机科学语境中引申为对资源消耗随规模变化的“复杂程度”进行度量，因此形成术语 space complexity（空间复杂度）。

相关词 Related Words

• Algorithm
• Asymptotic
• Big-O Notation
• Complexity
• Data Structure
• Memory
• Runtime
• Time Complexity

文学与经典著作 Notable Works

• Introduction to Algorithms（《算法导论》, Cormen / Leiserson / Rivest / Stein）：在分析章节中系统讨论时间复杂度与空间复杂度。
• The Art of Computer Programming（《计算机程序设计艺术》, Donald E. Knuth）：大量算法分析内容涉及空间使用与复杂度思想。
• Structure and Interpretation of Computer Programs（《计算机程序的构造和解释》, Abelson / Sussman）：在递归与过程抽象等主题中常引出对空间（如栈空间）增长的讨论。